数据库领域即将迎来革命？Jeff Dean 带队用机器学习颠覆数据索引方法
AI 科技评论按：伴随着机器学习理论和技术的发展、以及机器学习作为一门学科有越来越多的人关注以及参与，机器学习的落地应用场景也越来越多、越来越多样化。这两年的热门的应用大家都已非常熟悉，深度神经网络+强化学习下围棋的 AlphaGo，还有用深度神经网络做语音生成的 WaveNet，都是在传统方法研究已久但没有什么突破性进展的领域引入深度学习，用全新的思路、全新的工具达到了天神下凡一般令人惊叹的效果，稍加迭代更新以后更是尽善尽美。
近期，谷歌大脑也公开了一篇新的革命性论文，尝试把机器学习运用在传统上基于确定的规则和算法的数据库系统中，并且还取得了很好的初步成果：对于真实数据的索引任务，神经网络建立的索引可以比传统的缓存优化 B 树索引方法提高 70% 的速度，同时存储空间还能节省一个数量级。包括 Jeff Dean 在内的作者们也讨论并尝试了如何用神经网络承担数据库系统中更多不同的任务，他们觉得这是一个全新的、非常有潜力的研究和应用方向，很可能会影响未来的数据库系统的设计理念。AI 科技评论把这篇论文《The Case for Learned Index Structures》[https://arxiv.org/abs/1712.01208]（聊一聊学习得到的索引架构）的部分内容介绍如下。
从访问数据开始
对于计算机系统来说，只要有高效访问数据的需求，就可以建立一个索引结构。索引的思想发展到现在，也已经有了各种各样的方法可以处理各种不同的访问模式。举例来说，对于范围访问（比如读取某个时间段内的所有记录），B 树是最佳选择；对于基于键值的查询任务，哈希表方法的性能非常优秀；而如果要查询记录是否存在，Bloom Filter 就是多数时候的选择。由于索引在数据库系统以及其它一些应用中有着非常重要的作用，过去的十多年中各种索引方法就不断地得到更新改进，各种新方法对内存、缓存以及 CPU 资源的使用也越来越高效。
不过，目前所有的索引方法都仍然是通用型的数据结构，它们都假设数据是以最糟糕的方式分布的，而没有利用到真实数据中常常体现出的分布特点。比如，如果目标是构建一个高度定制化的系统，用于固定长度的、连续的整型（比如 1 一直到 1 亿这样）键值的存储和查询，这种时候用传统的 B 树对键值建立索引就不是一种好方法，因为键值自己就可以看作偏移量，对于查找任意键值、或者查找某个范围键值起始位置的任务，时间复杂度反倒从 O(log n) 提高到 了 O(1)；同样，把键值自己看作偏移量的话，索引所用的内存大小也可以从 O(n) 减少到 O(1)。可能有点惊人的是，其它的数据分布模式也都可以找到各自适合的优化方式。换个角度说，如果知道了数据的确切分布，不管数据库现在用的是什么样的索引方法，几乎都还可以做进一步的高度优化。
当然了，多数实际应用场景中的数据都不一定完美符合某个已知的数据分布，并且，如果为每一种使用状况都分别构建专用的解决方案的话，需要投入的成本也太高了。不过，这篇文章的作者们（包括 Jeff Dean 在内的四位谷歌研究员以及一位当时在谷歌访问的 MIT 学者）认为机器学习现在带来了一个全新的机会，它学到的模型可以反映数据的内在联系和分布模式。在此基础之上还可以进一步自动生成专用的索引结构，作者们称之为「学习得到的索引」（learned indexes），同时工程方面的成本也较低。
「学习得到的索引」是可能的、可用的
在这篇论文中，作者们探究了机器学习学到的模型（包括神经网络），能否用来替代 B 树、Bloom Filter 等这样的传统索引结构。这件事可能有点反直觉，因为传统索引方法往往需要有确定的语义保障，而机器学习通常提供不了这个；另外，神经网络虽然是最强大的一类机器学习模型，但同时人们也传统上认为评估它们效果所需的成本太高。不过作者们提出，这些明显的困难在实际中并没有看起来那么严重，而且恰恰相反，作者们提出的学习模型的方法很有潜力可以带来明显的好处，尤其是在为大规模矩阵运算设计的下一代硬件上。
具体来说，在语义保障方面，现代索引方法很大程度上已经是一些学到的模型，在这种现状下，把现有的模型替换成新的模型其实已经是一件非常简单直接的事情了，包括替换成神经网络也是一样。比如，一个 B 树索引可以看作是这样一个模型：它接收一个键值作为输入，然后预测对应的数据记录的位置；Bloom Filter 可以看作一个二值分类器，给定一个键值以后它可以预测这个键值是否存在。当然了，这其中也有一些细微但是非常重要的区别，比如现在的 Bloom Filter 可能会出现误报为真的情况，但不会出现误报为假。不过，这篇论文稍后将会展示出，借助新的学习技巧和/或简单的辅助数据结构，这些区别都是有可能得到解决的。
在性能方面，作者们观察到如今的 CPU 全都有强大的 SIMD（单指令多数据）计算能力，而且他们也推测许多笔记本电脑和手机很快都会有 GPU 或者 TPU。他们还推测，CPU-SIMD/GPU/TPU 都会变得越来越强大，因为相比通用指令集来说，这些处理器都能够更简便地扩大神经网络需要的非常有限的一部分数学运算的运算规模。那么运行神经网络所需的高计算力消耗未来就可能终于变得不值一提。举例来说，NVIDIA GPU 和谷歌 TPU 都可以在单个时钟循环内完成数千、甚至数万次神经网络的计算操作。更进一步地，已经有人指出，到 2025 年时 GPU 的速度还能再提升一千倍，到那时摩尔定律对于 CPU 已经基本失效了。只要把分支数量可观的索引结构替换为神经网络，数据库系统就可以从这样的硬件发展趋势中受益。
替代 B 树的机器学习模型理论上完全存在
这里我们重点介绍一下论文中神经网络学习得到的索引与 B 树索引之间的对比。
数据库的索引结构其实已经是一种模型，因为索引的作用就是给定键值之后「预测」这条记录所在的位置。假设这样一种情况，用 B 树对内存中的分析型数据库（也就是只读数据库）的有序主键建立索引，如下图 1(a)。在这种情况下，B 树索引提供了从要查询的键值到各条记录组成的有序数组中的一个位置的映射，同时能够保证记录数组中这个位置的键值和查询的键值相等或者大于查询的键值。值得一提的是，数据需要是有序的才能进行范围访问请求；并且，这种总体概念同样适用于二级索引，其中最下层是<键值，指针>对组成的列表，其中的键值就是被索引的属性，指针指向的就是数据记录。
为了让索引比较有效率，通常的做法中并不会对有序记录数组中的每一个键值都做索引，而是每隔 n 个记录做一个索引，这也就是每个分页中的第一个键值。这样可以显著减小索引中需要存储的数据量，同时性能下降非常轻微。正因为这样，B 树就是一个模型，用机器学习的术语的话可以把它称为回归树（regression tree）：它把一个键值映射到一个位置，它带有最大和最小误差（这里的最小误差为 0，最大误差是分页大小），同时只要这个值存在，就可以确保在这个范围内找到它。
那么接下来，我们就可以把这个索引机制用其它类型的机器学习模型替换掉，包括可以用深度学习模型替换，只要它们也同样可以提供类似的保证，确保数据只要存在就能在最小误差和最大误差组成的范围之间找到它。
第一眼看上去似乎很难找到有什么类型的机器学习模型可以提供这样的误差保证机制，但是它实际上出奇地容易。B 树其实只能对存储了的数据提供这种保证，而不能对所有可能的数据提供这样的保证。对于新增加的数据，B 树需要重新平衡——用机器学习的术语来说就是「重新训练」——之后才能提供同样的误差保证。这就可以大幅度简化问题：要提供保证的最小和最大误差就是模型对于训练数据（存储的数据）的最大误差。也就是说只需要做一件事，对每一个键值执行机器学习模型，然后记住位置预测时最糟糕的向上偏离值和向下偏离值。给定了一个键值以后，模型就会对在哪里找到这条数据做出预测；如果这个键值存在，那它就一定在预测的最小误差和最大误差定义出的范围内。接下来就可以把 B 树替换为任意一个具体类型的回归模型，包括线性回归或者神经网络，如上图 1(b) 所示。
在正式把 B 树更换为学习得到的索引之前，还是有一些技术方面的挑战需要解决的。比如，B 树对于插入和查询操作的计算成本是在有限的范围内的，而且能够非常好地利用缓存；同时，B 树可以把键值映射到并不连续映射在内存或者磁盘中的分页中；进一步地，如果要查询的键值在数据库中不存在，这样的模型返回的位置可能会在最小/最大误差范围之外，如果这不会单调地增加模型大小的话。所有这些特点都是有趣的挑战和研究课题。机器学习，尤其是神经网络有这样一种魔力，就是它们可以学习到许多种不同的数据分布、数据混合以及其它一些数据的模式以及奇怪的特点。那么，这里还剩下的明显的挑战，就是在模型的复杂度和准确度之间找到平衡，而作者们也提出了一些可能的解决方案。
实现一个「学习得到的索引」
一个朴素的全连接网络表现并不好
作者们首先尝试了一个朴素的方法，用 TensorFlow + Python 实现了一个具有两层全连接层、每层 32 个神经元的神经网络。用它为 200MB 的 web 服务器日志记录做二级索引，把时间作为输入特征、把位置作为网络预测的标签进行训练和测试。这样得到的模型执行一次就需要花费 8 万纳秒；相比之下 B 树只需要 300 纳秒时间，而且在键值空间中搜索的速度也要更快。
作者们认为这是由于以下几点原因：
TensorFlow 平台本身的设计目标是高效运行较大的模型，所以运行开销很大，尤其是搭配 Python 使用时；
B 树，或者决策树模型，总体来说逐次切分数据空间时非常高效；其它模型估计数据存在的总体累积概率密度的能力要更好，但是到了最后数据空间不大（统计规律开始变得不明显）时，速度就会变慢；
典型的机器学习优化目标是优化平均误差。然而对于索引任务，实际上更重要的是具体的最大误差和最小误差值；
B 树的缓存效率非常高，它总会缓存顶端的节点，然后再缓存一些其它需要的分页。相比之下神经网络就需要从内存中读取所有的权值才能完成一次运算。
为了克服这几个问题，展现出理论上可行的想法的实际可行性，作者们专门开发了这样几个方法帮助实现学习得到的索引。
Learning Index Framework
作者们编写了 Learning Index Framework，索引学习框架 LIF，可以把它看作一个索引生成系统：给定一种索引规格，LIF 就会生成不同的索引配置，并且优化它们、自动测试它们。LIF 可以借助 TensorFlow 中实现的更复杂的模型，边运行边学习简单的模型；同时它的推理过程并不依靠 TensorFlow，它会从学到的模型构建出高效的 C++编译版本，这样推理时可以大幅减少不必要的计算开销，运行时间缩减到了30纳秒级别。
The Recursive Model Index
Recursive model index，递归模型索引 RMI 是为了解决前面提到的数据空间变小以后模型预测能力变差的问题。举例来说，从 100M 条记录中寻找数据时，最大最小误差如果想要缩小到几百的数量级，只凭单个模型是非常难的；但同时，把误差缩小到 10k 的数量级，用这一个模型替代 B 树的最上两层就要简单得多，用简单的模型就可以做到。同样，下一层的模型只需要把误差从 10k 缩小到几百，由于它只需要关注数据的一个子集，所以也是一个较为简单的问题。
这样，作者们提出了递归模型索引 RMI。如图，作者们设计了层级化的网络结构，其中包含许多个模型，每一层中的模型都接收键值作为输入，然后据此选择下一层的模型，直到最后一层的模型对位置做出预测。在这里，每一个模型都可以看作是对键值空间的某一部分负责，在逐层选择的过程中逐渐降低了预测误差。作者们也证明了这样的模型是可以逐层训练，最终得到完整的网络的。
但同时值得注意的是，RMI 不是树模型。正如上图所示，不同的上层模型可以选择同一个下层模型；并且，其中的每个模型覆盖的数据范围并不是像 B 树那样固定的；最后，由于预测是靠不同模型间的选择完成的，所以对这个过程的理解不应该看作是“对位置的预测逐渐精确”，而是“逐次选择了对这个键值具有更好知识的模型”。
这种模型结构有这么几种好处：
数据分布的总体形状是更容易学的，这样的模型结构就利用了这个规律；
这样的模型可以高效地把数据空间分割成了多个小空间，从而用更少的操作提高了最后数据空间很小时的预测精度；
网络中不同的层之间不需要任何搜索操作。比如，模型 1.1 的输出直接就选择出了下一层的模型 1.2。这不仅减少了管理整个结构所需的指令的数目，而且还可以把整个索引表达成可以在 TPU/GPU 上完成的矩阵相乘操作；
这样的结构可以允许混用不同的模型。比如最上层的模型可以是使用 ReLU 激活函数的神经网络，因为它们通常可以学到很多种不同的复杂数据分布；底层的模型就可以是数千个简单的线性回归模型，因为它们需要的空间和执行时间都很少。
混用模型的网络和它的训练
这篇论文中作者们就编写算法训练了一个不同模型组成的 RMI 网络。具体来说，其中的单个模型可以是带有 0 到 2 层全连接层和 ReLU 激活函数的简单神经网络，每层最大宽度为 32 个神经元；也可以是 B 树，也就是决策树。想要其它类型的模型也可以，这里作者们先用了这两类。
根据作者们的设计，每个模型的标准最小/最大误差会存储在最下面一层的模型中，这种做法带来的好处是可以根据使用的模型为每个键值单独设定搜索空间的大小。作者们也为混用模型网络中设计了一个替换功能，一开始网络中所有模型都是神经网络，而如果某处神经网络模型的绝对最小/最大误差高于某个阈值的话，训练算法就会把这个神经网络模型替换成 B 树。这样实际上也就是设定了这个混用模型网络的表现的下限：对于最糟糕的、无法学习的数据分布，混用模型网络就基本上是一个 B 树模型；而在除此之外的情况下，模型都理应有更好的表现。
测试结果
作者们在几个数据集上把学到的索引模型和 B 树模型进行了对比。B 树模型选用了不同的分页大小；而学到的索引模型选用了一个 2 层的 RMI 模型，测试中也给出了不同的第二阶段模型搜索数量大小的表现。对于模型结构，第二阶段的模型实际上在结构最简单（0 个全连接层），基本就是线性模型的时候有最好的表现；这也并不奇怪，因为搜索空间已经减小之后，运行更复杂的模型反倒不划算。整个学到的索引模型用 LIF 编译之后，运行在不带有 GPU/TPU 的英特尔 E5 CPU 上。
Weblogs 数据集包含近几年中某个大学网站的 200M 条访问记录，每条记录都有不同的时间戳。这个数据集几乎可以算是最糟糕的情况了，因为它的数据模式会受到课程规划、周末、节假日、午餐、学院活动、放假时间等等因素的影响，非常难以学习。
而实际测试结果显示出，与 B 树相比，学到的索引模型不仅总是更快，消耗的空间也最多可以节省 99%，也就是两个数量级。
地图数据集包含了大约 200M 条用户添加的全世界的地标信息。这个数据集的数据就更线性、不规律性更小。所以学习得到的索引相比 Weblogs 数据集中更好的表现，不仅可以提速超过 60%、大小减小最多 99%，最大预测误差也减小了很多。
这样的结果不仅有力地验证了论文开头作者们提出的「当数据有规律时，机器学习的方法可以优化索引效率」的猜想，而且初步实验的效果就出人意料地好。
能够学习得到新的索引模式之后
值得说明的是，作者们并没有打算用学到的索引完全取代传统的索引架构。实际上，他们是想要指出一种新的建立索引方式，它应当是现有研究的补充，而且为已经有几十年历史的数据库索引领域开启了一个全新的研究方向（当然这也还有待更多后续研究和讨论）。
这篇论文中作者们的研究重点在于纯读取负载（键值查找、数据定位、存在性搜索），同时也大概讨论了如何把这种思路拓展到重写入负载的系统的加速上。作者们也进一步简要描述了如何用同样的思想把数据库系统的其它组件和操作也做个替换，包括排序和合并。如果这些研究的进展顺利的话，这可能会发展成脱离现有数据库系统模式的新做法，高维度索引、学习数据库操作算法、GPU/TPU 加速数据库操作都会是有意思而且有深远实用意义的研究目标。
总的来说，作者们表明了机器学习学到的模型有潜力在现有的顶级数据库索引方法基础上继续带来显著的提高，这不仅是数据库相关技术研究的新方向，更是机器学习在又一个新领域拓土开疆。
论文地址：https://arxiv.org/abs/1712.01208 ，AI 科技评论编译
————— 新人福利 —————
关注AI 科技评论，回复 1 获取
【数百 G 神经网络 / AI / 大数据资源，教程，论文】
————— AI 科技评论招人了 —————
AI 科技评论期待你的加入，和我们一起见证未来！
现诚招学术编辑、学术兼职、学术外翻
详情请点击招聘启事
————— 给爱学习的你的福利 —————
AI慕课年度学习盛典
爆款课程限时打折，优惠卡券免费领取
精品课程1元秒杀，买课即送热门图书
点击阅读原文，即刻获取优惠
▼▼▼
————————————————————